翻訳と辞書 Words near each other ・ Iterated limit ・ Iterated local search ・ Iterated logarithm ・ Iterated monodromy group ・ Iteratee ・ ITerating ・ Iteration ・ Iteration (disambiguation) ・ Iteration mark ・ Iterations of I ・ Iterative and incremental development ・ Iterative aspect ・ Iterative closest point ・ Iterative compression ・ Iterative deepening A* ・ Iterative deepening depth-first search ・ Iterative design ・ Iterative impedance ・ Iterative learning control ・ Iterative method ・ Iterative proportional fitting ・ Iterative Receiver Design ・ Iterative reconstruction ・ Iterative refinement ・ Iterative Template Library ・ Iterative Viterbi decoding ・ Iteratively reweighted least squares ・ Iterator ・ Iterator pattern ・ Iteri language Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Iterative deepening depth-first search ： ウィキペディア英語版 Iterative deepening depth-first search In computer science, iterative deepening depth-first search (IDDFS) is a state space search strategy in which a depth-limited search is run repeatedly, increasing the depth limit with each iteration until it reaches $d$, the depth of the shallowest goal state. IDDFS is equivalent to breadth-first search, but uses much less memory; on each iteration, it visits the nodes in the search tree in the same order as depth-first search, but the cumulative order in which nodes are first visited is effectively breadth-first. == Properties == IDDFS combines depth-first search's space-efficiency and breadth-first search's completeness (when the branching factor is finite). It is optimal when the path cost is a non-decreasing function of the depth of the node. The time complexity of IDDFS is $O(b^d)$ and its space complexity is $O(d)$, where $b$ is the branching factor and $d$ is the depth of the shallowest goal.〔http://www.cse.sc.edu/~mgv/csce580f09/gradPres/korf_IDAStar_1985.pdf〕 Since iterative deepening visits states multiple times, it may seem wasteful, but it turns out to be not so costly, since in a tree most of the nodes are in the bottom level, so it does not matter much if the upper levels are visited multiple times. The main advantage of IDDFS in game tree searching is that the earlier searches tend to improve the commonly used heuristics, such as the killer heuristic and alpha-beta pruning, so that a more accurate estimate of the score of various nodes at the final depth search can occur, and the search completes more quickly since it is done in a better order. For example, alpha-beta pruning is most efficient if it searches the best moves first.〔 A second advantage is the responsiveness of the algorithm. Because early iterations use small values for $d$, they execute extremely quickly. This allows the algorithm to supply early indications of the result almost immediately, followed by refinements as $d$ increases. When used in an interactive setting, such as in a chess-playing program, this facility allows the program to play at any time with the current best move found in the search it has completed so far. This can be phrased as each depth of the search ''co''recursively producing a better approximation of the solution, though the work done at each step is recursive. This is not possible with a traditional depth-first search, which does not produce intermediate results. The time complexity of IDDFS in well-balanced trees works out to be the same as Depth-first search: $O(b^)$. In an iterative deepening search, the nodes on the bottom level are expanded once, those on the next to bottom level are expanded twice, and so on, up to the root of the search tree, which is expanded $d+1$ times.〔 So the total number of expansions in an iterative deepening search is :$(d)b\; +\; (d-1)b^\; +\; \backslash cdots\; +\; 3b^\; +\; 2b^\; +\; b^$ :$\backslash sum\_^d\; (d+1-i)b^i$ For $b=10$ and $d=5$ the number is : 50 + 400 + 3,000 + 20,000 + 100,000 = 123,450 All together, an iterative deepening search from depth 1 to depth $d$ expands only about 11% more nodes than a single breadth-first or depth-limited search to depth $d$, when $b=10$. The higher the branching factor, the lower the overhead of repeatedly expanded states, but even when the branching factor is 2, iterative deepening search only takes about twice as long as a complete breadth-first search. This means that the time complexity of iterative deepening is still $O(b^d)$, and the space complexity is $O(d)$ like a regular depth-first search. In general, iterative deepening is the preferred search method when there is a large search space and the depth of the solution is not known.〔 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Iterative deepening depth-first search」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.